const std = @import("std");
const mem = std.mem;
const math = std.math;

// 假设这些模块和函数已在您的项目中定义。
const lbmath = @import("./matrix/math/lbmath.zig");
const threed_geometry_tool = @import("./threed_geometry_tool.zig");
// 下面是合并两个error集合
// pub const SubdivisionError = error{
//     OutputSliceTooSmall,
//     NoValidEarFound,
// } || lbmath.Math_Compute_Abandon;

fn SubPolyVer(comptime T: type) type {
    return struct {
        p: []const T,
        i: u32,
        score: T = -2.0,
        update: bool = true,
    };
}

/// 计算一个三角形角度的分数。
fn compute_one_angle(
    comptime T: type,
    p1: []const T,
    p2: []const T,
    p3: []const T,
    n: *[3]T,
) T {
    var dir1: [3]T = .{ p3[0] - p2[0], p3[1] - p2[1], p3[2] - p2[2] };
    var dir2: [3]T = .{ p1[0] - p2[0], p1[1] - p2[1], p1[2] - p2[2] };

    lbmath.normalize(&dir1) catch return 2;
    lbmath.normalize(&dir2) catch return 2;

    const n1 = lbmath.out_product(&dir1, &dir2);
    var score = lbmath.inner_product(&dir1, &dir2); // score = cos(theta)

    if (lbmath.inner_product(&n1, n) < 0) {
        score += 3;
    } else {
        score = 1 - score;
    }

    return score;
}

/// 计算多边形中一个顶点的“耳朵分数”。
fn compute_score_in_polygon(
    comptime T: type,
    spvs: []const SubPolyVer(T),
    n: *const [3]T,
    i: usize,
) T {
    const len = spvs.len;

    // 1. 计算四个不同组合的角度，并取最小值
    // 组合 1: (p[i], p[i+1], p[i-1])
    var p_idx_1 = i;
    var p_idx_2 = (i + 1) % len;
    var p_idx_3 = (i + len - 1) % len;
    var score = compute_one_angle(T, spvs[p_idx_1].p, spvs[p_idx_2].p, spvs[p_idx_3].p, n);
    // 说明i i+1 i-1是凹的，也就是三角形i-1 i i+1是凹的
    if (score >= 2) return -1;
    //如果不是凹，那就是凸的，所以三角形i-1 i i+1是凸的，所以后面不用再验证是否凸了
    //
    // 组合 2: (p[i-1], p[i+1], p[i+2])
    p_idx_1 = (i + len - 1) % len;
    p_idx_2 = (i + 1) % len;
    p_idx_3 = (i + 2) % len;
    var temp_score = compute_one_angle(T, spvs[p_idx_1].p, spvs[p_idx_2].p, spvs[p_idx_3].p, n);
    // 下面判断角i-1 i+1 i+2和上面的角 i i+1 i-1重合.
    if (temp_score >= 4 - score) return -1;
    if (temp_score < score) score = temp_score;

    // 组合 3: (p[i+1], p[i-1], p[i])
    p_idx_1 = (i + 1) % len;
    p_idx_2 = (i + len - 1) % len;
    p_idx_3 = i;
    const temp_score1 = compute_one_angle(T, spvs[p_idx_1].p, spvs[p_idx_2].p, spvs[p_idx_3].p, n);
    // // 下面判断说明 i+1 i-1 i是凹的，也就是三角形i i+1 i-1是凹的,
    // // 但是由于上面判断过了，所以这里省略
    // if(temp_score >=2) return -1
    if (temp_score1 < score) score = temp_score1;

    // 组合 4: (p[i-2], p[i-1], p[i+1])
    p_idx_1 = (i + len - 2) % len;
    p_idx_2 = (i + len - 1) % len;
    p_idx_3 = (i + 1) % len;
    temp_score = compute_one_angle(T, spvs[p_idx_1].p, spvs[p_idx_2].p, spvs[p_idx_3].p, n);
    // 下面判断角i-2 i-1 i+1和上面的角 i+1 i-1 i重合.
    if (temp_score >= 4 - temp_score1) return -1;

    if (temp_score < score) score = temp_score;

    // 2. 检查是否有其他顶点位于三角形 (p[j], p[i], p[k]) 内部
    const j = (i + len - 1) % len;
    const k = (i + 1) % len;
    const p_j = spvs[j].p;
    const p_i = spvs[i].p;
    const p_k = spvs[k].p;

    for (spvs, 0..) |spv, ii| {
        if (ii == i or ii == j or ii == k or
            ii == (i - 2 + len) % len or ii == (i + 2) % len)
        {
            continue;
        }
        const p_ii = spv.p;

        var dir1: [3]T = .{ p_ii[0] - p_j[0], p_ii[1] - p_j[1], p_ii[2] - p_j[2] };
        var dir2: [3]T = .{ p_ii[0] - p_i[0], p_ii[1] - p_i[1], p_ii[2] - p_i[2] };
        var dir3: [3]T = .{ p_ii[0] - p_k[0], p_ii[1] - p_k[1], p_ii[2] - p_k[2] };

        const tn1 = lbmath.out_product(&dir1, &dir2);
        const tn2 = lbmath.out_product(&dir2, &dir3);
        const tn3 = lbmath.out_product(&dir3, &dir1);

        if (lbmath.inner_product(&tn1, &tn2) >= 0 and
            lbmath.inner_product(&tn1, &tn3) >= 0 and
            lbmath.inner_product(&tn2, &tn3) >= 0)
        {
            return -1.0;
        }
    }

    return score;
}

/// 通过一次裁剪一个“耳朵”的方式，递归地对多边形进行三角剖分。
fn subdivision_of_polygon_recursive(
    comptime T: type,
    spvs: []SubPolyVer(T),
    s: [][3]u32,
    n: *const [3]T,
) usize {
    const len = spvs.len;
    if (len < 3) {
        return 0;
    }
    if (len == 3) {
        // try triangles.append(.{ spvs_list.items[0].i, spvs_list.items[1].i, spvs_list.items[2].i });
        s[0][0] = spvs[0].i;
        s[0][1] = spvs[1].i;
        s[0][2] = spvs[2].i;
        return 1;
    }

    var best_score: T = -2.0;
    var ear_idx: ?usize = null;

    for (spvs, 0..) |*spv, i| {
        if (spv.update) {
            spv.score = compute_score_in_polygon(T, spvs, n, i);
            spv.update = false;
        }
        if (spv.score > best_score) {
            best_score = spv.score;
            ear_idx = i;
        }
    }

    if (ear_idx) |an| {
        const ia_idx = (an + len - 1) % len;
        const ib_idx = (an + 1) % len;

        s[0][0] = spvs[ia_idx].i;
        s[0][1] = spvs[an].i;
        s[0][2] = spvs[ib_idx].i;

        spvs[ia_idx].update = true;
        spvs[ib_idx].update = true;

        for (an..(len - 1)) |i| {
            spvs[i] = spvs[i + 1];
        }
        const re = 1 + subdivision_of_polygon_recursive(T, spvs[0 .. len - 1], s[1..], n);
        return re;
    } else {
        return 0;
    }
}

/// 将一个嵌入在3D空间中的简单多边形进行三角剖分。
pub fn subdivision_of_polygon(
    comptime T: type,
    allocator: mem.Allocator,
    v: [][]const T,
    s: [][3]u32,
) !usize {
    const len = v.len;
    if (len < 3) return 0;
    if (s.len < len - 2) return lbmath.Math_Compute_Abandon.Math_Compute_Abandon;

    const n = threed_geometry_tool.compute_plane_normal_of_jordan_curve(v);

    const spvs = try allocator.alloc(SubPolyVer(T), len);
    defer allocator.free(spvs);
    for (v, 0..) |p, i| {
        // try spvs_list.append(.{ .p = p, .i = @intCast(i) });
        spvs[i] = .{ .p = p, .i = @intCast(i), .update = true, .score = -2 };
    }

    return subdivision_of_polygon_recursive(T, spvs, s[0..], &n);
}

//  应该写个优化版本的剖分函数，用来合并距离过近的点
// 防止出现过近的点，稍微越界，导致计算失败，所以要合并过近点
//
//
pub fn optimized_subdivision_of_polygon(
    comptime T: type,
    allocator: mem.Allocator,
    v: [][]const T,
    s: [][3]u32,
) !usize {
    const len = v.len;
    if (len < 3) return 0;
    if (s.len < len - 2) return lbmath.Math_Compute_Abandon.Math_Compute_Abandon;

    const n = threed_geometry_tool.compute_plane_normal_of_jordan_curve(v);

    const spvs = try allocator.alloc(SubPolyVer(T), len);
    defer allocator.free(spvs);
    for (v, 0..) |p, i| {
        // try spvs_list.append(.{ .p = p, .i = @intCast(i) });
        spvs[i] = .{ .p = p, .i = @intCast(i), .update = true, .score = -2 };
    }

    return subdivision_of_polygon_recursive(T, spvs, s[0..], &n);
}

//对于带插入边的多边形剖分算法，判断边是否和三角形相交时，应该
//采取严格判断，即只要相交哪怕一点都算相交，然后删除
// 并先“生长”插入边，形成两个多边形区域，然后再剖分
//
